1977B - Binary Colouring - CodeForces Solution

def check_highest_2(x):
    i = 31
    while i >= 0:
        if 2 ** i <= x:
            return i
        i -= 1

def recur(x, ans, isminus):
        if x <= 0:
        return True
    temp = check_highest_2(x)
    done = True
    done2 = True
    for num in ans:
        if num[1] == temp+1:
            done = False
        if num[1] == temp+2 or num[1] == temp + 1:
            done2 = False
    if done:   
        if isminus:
            ans.append((-1, temp))
        else:
            ans.append((1, temp))
        
        if recur(x - 2 ** temp, ans, isminus) == True:
            return True
        ans.pop()
    if done2:
        if isminus:
            ans.append((-1, temp+1))
        else:
            ans.append((1, temp+1))
        
        if recur(2 ** (temp+1) - x, ans, not isminus) == True:
            return True
        ans.pop()
    return False

    
def solve():
    ans = []
    x = int(input())

    recur(x, ans, False)
    temp_ans = [0] * (32)
    for num in ans:
        temp_ans[num[1]] = num[0]
    print(32)
    print(* temp_ans)

for i in range(int(input())):
    solve()